package hot100.logos51To60;

import java.util.*;

/**
 * @author logos
 * date 2025/7/15 12:28
 * @version v1.0
 * @Package hot100.logos51To60
 */
public class logos53 {

    /**
     * 53.课程表
     * https://leetcode.cn/problems/course-schedule/?envType=study-plan-v2&envId=top-100-liked
     */

    class Solution {
        private static int MAX_N = 2001;

        private static int MAX_M = 5005;

        private static int[] head = new int[MAX_N];

        private static int[] next = new int[MAX_M];

        private static int[] to = new int[MAX_M];

        private static int cnt;

        private static int[] que = new int[MAX_N];

        private static int l, r;

        private static void addEdge(int u, int v) {
            next[cnt] = head[u];
            to[cnt] = v;
            head[u] = cnt++;
        }

        private static void build(int n) {
            cnt = 1;
            l = r = 0;
            Arrays.fill(head, 0, n + 1, 0);
        }

        public boolean canFinish(int numCourses, int[][] prerequisites) {
            build(numCourses);
            int[] in = new int[numCourses];
            for (int[] x : prerequisites) {
                addEdge(x[1], x[0]);
                in[x[0]]++;
            }
            for (int i = 0; i < numCourses; i++) {
                if (in[i] == 0) {
                    que[r++] = i;
                }
            }
            int ans = 0;
            while (l < r) {
                int tmp = que[l++];
                ans++;
                for (int ei = head[tmp]; ei > 0; ei = next[ei]) {
                    if (--in[to[ei]] == 0) {
                        que[r++] = to[ei];
                    }
                }
            }
            return ans == numCourses;
        }
    }


    class Solution2 {
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            int[] in = new int[numCourses];
            List<List<Integer>> g = new ArrayList<>();
            Queue<Integer> que = new LinkedList<>();
            for(int i = 0; i < numCourses; i++) {
                g.add(new ArrayList<>());
            }
            for(int[] cp : prerequisites) {
                in[cp[0]]++;
                g.get(cp[1]).add(cp[0]);
            }
            for(int i = 0; i < numCourses; i++) {
                if(in[i] == 0) {
                    que.add(i);
                }
            }
            while(!que.isEmpty()) {
                int tmp = que.poll();
                numCourses--;
                for(int cur : g.get(tmp)) {
                    if(--in[cur] == 0) {
                        que.add(cur);
                    }
                }
            }
            return numCourses == 0;
        }
    }

}
